package com.atguigu.dp;

import java.util.Arrays;

/**
 * 01背包问题
 */
public class BagDemo {

    public static void main(String[] args) {
        int[] itemWeightArr={1,4,3};
        int[] itemValueArr={1500,3000,2000};
        int maxAllowWeight=4;

        int maxValue = maxValue(itemWeightArr, itemValueArr, maxAllowWeight);
        System.out.println(maxValue);

    }

    /**
     * 最大价值
     * 同时要求, 将maxAllowWeight以下的所有情况打印下来
     * @param itemWeightArr 道具重量数组
     * @param itemValueArr 道具价值数组
     * @param maxAllowWeight 最大允许容量
     */
    public static int maxValue(int[] itemWeightArr,int[] itemValueArr,int maxAllowWeight){
        // 第一索引为道具数量, 第二索引为允许重量, 值为最大价值
        int[][] itemCountAndAllowWeight2MaxValueArr=new int[itemWeightArr.length+1][maxAllowWeight+1];
        // 所使用的道具
        int[][][] useItemArr=new int[itemWeightArr.length+1][maxAllowWeight+1][itemWeightArr.length];

        // 将边界0情况填充说明: itemCount=0时, 均为0; allowWeight=0时, 均为0. 实际不需任何处理

        // 以下为前两行的逻辑模拟
//        // 从itemCount=1, allowWeight=1开始, 逐次增加allowWeight, 填充实际的最大价值
//        int itemCount=1;
//        for(int allowWeight=1;allowWeight<=maxAllowWeight;allowWeight++){
//            if(itemWeightArr[itemCount-1]<allowWeight){
//                itemCountAndAllowWeight2MaxValueArr[itemCount][allowWeight]=0;
//            }else{
//                itemCountAndAllowWeight2MaxValueArr[itemCount][allowWeight]=itemValueArr[0];
//            }
//        }
//
//        // 从itemCount=2, allowWeight=1开始, 逐次增加allowWeight, 填充实际最大值
//        itemCount=2;
//        for(int allowWeight=1;allowWeight<=maxAllowWeight;allowWeight++){
//            if(itemWeightArr[itemCount-1]<allowWeight){
//                itemCountAndAllowWeight2MaxValueArr[itemCount][allowWeight]=itemCountAndAllowWeight2MaxValueArr[itemCount-1][allowWeight];
//            }else{
//                itemCountAndAllowWeight2MaxValueArr[itemCount][allowWeight]=Math.max(
//                        itemValueArr[itemCount-1]+itemCountAndAllowWeight2MaxValueArr[itemCount-1][allowWeight-itemWeightArr[itemCount-1]],
//                        itemCountAndAllowWeight2MaxValueArr[itemCount-1][allowWeight]);
//            }
//        }

        // 从itemCount=n, allowWeight=1开始, 逐次增加allowWeight, 填充实际最大价值
        for(int itemCount=1;itemCount<=itemWeightArr.length;itemCount++){
            for(int allowWeight=1;allowWeight<=maxAllowWeight;allowWeight++){
                if(itemWeightArr[itemCount-1]>allowWeight){
                    itemCountAndAllowWeight2MaxValueArr[itemCount][allowWeight]=itemCountAndAllowWeight2MaxValueArr[itemCount-1][allowWeight];
                    System.arraycopy(useItemArr[itemCount - 1][allowWeight], 0, useItemArr[itemCount][allowWeight], 0, itemWeightArr.length);
                }else{
                    int oldValue = itemCountAndAllowWeight2MaxValueArr[itemCount - 1][allowWeight];
                    int newValue = itemValueArr[itemCount - 1] + itemCountAndAllowWeight2MaxValueArr[itemCount - 1][allowWeight - itemWeightArr[itemCount - 1]];
                    if(oldValue>=newValue){
                        itemCountAndAllowWeight2MaxValueArr[itemCount][allowWeight]=oldValue;
                        System.arraycopy(useItemArr[itemCount - 1][allowWeight], 0, useItemArr[itemCount][allowWeight], 0, itemWeightArr.length);
                    }else{
                        itemCountAndAllowWeight2MaxValueArr[itemCount][allowWeight]=newValue;
                        System.arraycopy(useItemArr[itemCount - 1][allowWeight-itemWeightArr[itemCount-1]], 0, useItemArr[itemCount][allowWeight], 0, itemWeightArr.length);
//                        useItemArr[itemCount][allowWeight]=Arrays.copyOf(useItemArr[itemCount-1][allowWeight-itemWeightArr[itemCount-1]],itemWeightArr.length);
                        useItemArr[itemCount][allowWeight][itemCount-1]=1;
                    }
//                    itemCountAndAllowWeight2MaxValueArr[itemCount][allowWeight]=Math.max(oldValue, newValue);

                }
            }
        }

        // 此处将所有情况打印
        for(int i=0;i<itemCountAndAllowWeight2MaxValueArr.length;i++){
            for(int j=0;j<itemCountAndAllowWeight2MaxValueArr[i].length;j++){
                System.out.printf("%d\t",itemCountAndAllowWeight2MaxValueArr[i][j]);
            }
            System.out.println();
        }

        // 此处打印最后一步放置的道具数
        for(int i=0;i<itemCountAndAllowWeight2MaxValueArr.length;i++){
            for(int j=0;j<itemCountAndAllowWeight2MaxValueArr[i].length;j++){
                System.out.printf("%s\t",Arrays.toString(useItemArr[i][j]));
            }
            System.out.println();
        }


        return itemCountAndAllowWeight2MaxValueArr[itemWeightArr.length][maxAllowWeight];
    }
}
